"""
基本排序算法示例
冒泡排序、选择排序、插入排序、快速排序
"""


class Sort:
    def __init__(self, list_):
        self.list_ = list_

    def bubble(self, func_condition):
        """
        冒泡排序
        :return:
        """
        # 　外层循环表示比较多少轮
        for i in range(len(self.list_) - 1):
            # 　内层循环表示每轮比较的次数
            for j in range(len(self.list_) - i - 1):
                # 前一个数比后一个数大则交换位置
                if func_condition(self.list_[j], self.list_[j + 1]):
                    self.list_[j], self.list_[j + 1] = \
                        self.list_[j + 1], self.list_[j]

    def select(self, func_condition):
        """
        选择排序
        :return:
        """
        # 　比较多少轮
        for i in range(len(self.list_) - 1):
            select_min = i  # 假定i号位置数字最小
            for j in range(i + 1, len(self.list_)):
                if func_condition(self.list_[select_min], self.list_[j]):
                    select_min = j
            if i != select_min:
                self.list_[i], self.list_[select_min] = \
                    self.list_[select_min], self.list_[i]

    def straight_insertion_sort(self, func_condition):
        """
        直接插入排序
        :return:
        """
        for i in range(1, len(self.list_)):
            x = self.list_[i]
            j = i
            while j > 0 and func_condition(self.list_[j - 1], x):
                self.list_[j] = self.list_[j - 1]
                j -= 1
            self.list_[j] = x

    def binary_inserted_sort(self, func_condition):
        """
        折半排序
        :param func_condition: lambda 函数;示例lambda e1,e2:e1 > e2;大于号为递增，小于号为递减
        :return:
        """
        for i in range(1, len(self.list_)):
            b = self.list_[i]  # 将需要移动元素暂存起来
            low = 0  # 折半查找开始位置
            high = i - 1  # 折半查找结束位置
            while low <= high:  # 折半查找循环
                mid = int((low + high) / 2)  # 中间点
                if func_condition(self.list_[mid], b):  # 这里大于号-->递增，相反递减
                    high = mid - 1  # 查找左半子表
                else:
                    low = mid + 1  # 查找右半子表
            j = i - 1
            while j >= (high + 1):  # 查找结束后移动操作
                self.list_[j + 1] = self.list_[j]
                j -= 1
            self.list_[high + 1] = b

    def shell_sort(self):
        pass

    # 一轮交换
    def __sub_sort(self, low, high):
        key = self.list_[low]  # 基准数字
        while low < high:
            # 　后面的数向前甩
            while low < high and self.list_[high] >= key:
                high -= 1
            self.list_[low] = self.list_[high]
            # 　前面的数向后甩
            while low < high and self.list_[low] < key:
                low += 1
            self.list_[high] = self.list_[low]
        self.list_[low] = key
        return low

    # 　快排函数
    def quick(self, low, high):
        # 　low 列表开头元素索引
        #   high 列表结尾元素索引
        if low < high:
            key = self.__sub_sort(low, high)
            self.quick(low, key - 1)
            self.quick(key + 1, high)


if __name__ == "__main__":
    s = Sort([3, 2, 1, 4, 3, 5, 7, 8, 10])
    s.bubble(lambda e1, e2: e1 < e2)
    print(s.list_)
